package algorithm.dynamic_planning.leetcode;

import java.util.Arrays;

/**
 * @author yuisama
 * @date 2022/12/05 15:11
 * 最长递增子序列 - LIS
 **/
public class Num300_LIS {
    // 1.常规dp解法
    // dp[i] 定义为以nums[i]这个数结尾的最长递增子序列长度
    // base case. dp[i] 初始化为1,因为以nums[i]结尾的最长子序列至少包含自己
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        // 1.base case dp[i] = 1
        Arrays.fill(dp,1);
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    // 当前nums[i] 可以拼接在以nums[j]结尾的最大子序列后，形成新的最大子序列
                    // dp[i]就是这些新的子序列中的最大值
                    dp[i] = Math.max(dp[i],dp[j] + 1);
                }
            }
        }
        // 2.dp[]数组存储了每个元素结尾的最大子序列长度，整个数组的LIS就是其中的最大值
        int res = 0;
        for (int i : dp) {
            res = Math.max(res,i);
        }
        return res;
    }
}